package com.zwj.interview.链表;

/**
 * 给定一个链表，链表中节点的顺序是L0→L1→L2→…→Ln-1→Ln，请问如何重排链表使节点的顺序变成L0→Ln→L1→Ln-1→L2→Ln-2→…？
 * <p>
 * 需要首先解决的问题是如何把一个链表分成两半。如果能够找到链表的中间节点，
 * 那么就能根据中间节点把链表分割成前后两半。位于中间节点之前的是链表的前半段，位于中间节点之后的是链表的后半段
 * <p>
 * 可以使用双节点来寻找链表的中间节点。如果一快一慢两个指针同时从链表的头节点出发，
 * 快的指针一次顺着next指针向前走两步，而慢的指针一次只走一步，
 * 那么当快的指针走到链表的尾节点时慢的指针刚好走到链表的中间节点
 * <p>
 * <p>
 * 一个值得注意的问题是，链表的节点总数既可能是奇数也可能是偶数。
 * 当链表的节点总数是奇数时，就要确保链表的前半段比后半段多一个节点
 * 拿到中点是关键，然后将前后两部分断开，翻转后半部分，再进行连接
 */
public class 链表重排序 {


    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        //拿到中点
        ListNode mid = middleNode(head);
        ListNode l1 = head;
        //后半部分的起点
        ListNode l2 = mid.next;
        //断开前后两部分链表
        mid.next = null;
        //反转后半部分
        l2 = reverseList(l2);
        mergeList(l1, l2);
    }


    //拿到中点
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


   //连接两个链表
    public void mergeList(ListNode l1, ListNode l2) {
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (l1 != null && l2 != null) {
            //先暂存连个节点的下一个节点
            l1_tmp = l1.next;
            l2_tmp = l2.next;
            //往后推进
            l1.next = l2;
            //推进l1
            l1 = l1_tmp;

            l2.next = l1;
            //推进l2
            l2 = l2_tmp;
        }
    }

    //合并两个链表
    public void mergeList2(ListNode l1, ListNode l2) {
        ListNode l1_tmp;
        ListNode l2_tmp;
        while(l1!=null && l2!=null){
            //先记住两个链表的下一个节点
            l1_tmp=l1.next;
            l2_tmp=l2.next;
            l1.next=l2;
            l1=l1_tmp;

            l2.next=l1;
            l2=l2_tmp;

        }

    }

    public ListNode reverseList(ListNode head) {
        //1、变量prev指向当前节点的前一个节点
        ListNode prev = null;
        //2、变量cur指向当前遍历到的节点
        ListNode cur = head;
        while (cur != null) {
            //3、变量next指向当前节点的下一个节点
            ListNode next = cur.next;
            //真正执行反转
            cur.next = prev;
            prev = cur;
            cur = next;

        }
        return prev;
    }

}
